package com.cuz.daileetcode;


import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

public class Day54 {

    static class S1 {
        static boolean solution2(String s1, String s2) {
            if (s1 == null || s2 == null) {
                return false;
            }
            int len1 = s1.length();
            int len2 = s2.length();
            if (len1 != len2) {
                return false;
            }
            if (KMP.kmpIndexOf(s1 + s1, s2) != -1) {
                return true;
            }
            return false;
        }

        static boolean solution1(String s1, String s2) {
            if (s1 == null || s2 == null) {
                return false;
            }
            int len1 = s1.length();
            int len2 = s2.length();
            if (len1 != len2) {
                return false;
            }
            for (int index = 1; index < len1 - 1; index++) {
                if (KMP.kmpIndexOf(rotateString(s1, index), s2) != -1) {
                    return true;
                }
            }
            return false;
        }

        static String rotateString(String str1, int from) {
            String prefix = str1.substring(from);
            String suffix = str1.substring(0, from);
            return prefix + suffix;
        }
    }

    static class KMP {
        static int kmpIndexOf(String source, String target) {
            if (source == null || target == null) {
                return -1;
            }
            int sourceLen = source.length();
            int targetLen = target.length();
            if (sourceLen < targetLen) {
                return -1;
            }
            int[] kmpHelpArray = kmpHelpArray(target);
            int sourceIndex = 0;
            int targetIndex = 0;
            char[] targetCharArray = target.toCharArray();
            char[] sourceCharArray = source.toCharArray();
            while (sourceIndex < sourceLen && targetIndex < targetLen) {
                if (targetCharArray[targetIndex] == sourceCharArray[sourceIndex]) {
                    targetIndex++;
                    sourceIndex++;

                } else if (kmpHelpArray[targetIndex] == -1) {
                    sourceIndex++;
                } else {
                    targetIndex = kmpHelpArray[targetIndex];
                }
            }
            if (targetIndex == targetLen) {
                return sourceIndex - targetIndex;
            }
            return -1;
        }

        static int[] kmpHelpArray(String str) {
            int len = str.length();
            if (len == 1) {
                return new int[-1];
            }
            if (len == 2) {
                return new int[]{-1, 0};
            }
            int valueOfIndex2 = str.charAt(0) == str.charAt(1) ? 1 : 0;
            if (len == 3) {
                return new int[]{-1, 0, valueOfIndex2};
            }
            int[] dp = new int[len];
            dp[0] = -1;
            dp[1] = 0;
            dp[2] = valueOfIndex2;
            char[] charArray = str.toCharArray();
            for (int index = 3; index < len; index++) {
                maxPreSuffixEqualLenSet(dp, index, charArray);
            }
            return dp;
        }

        static void maxPreSuffixEqualLenSet(int[] dp, int index, char[] charArray) {
            //当前位置最长前后缀，依赖于上一个字符的dp信息
            int preCharIndex = index - 1;
            //如果没有到0
            while (preCharIndex > 0) {
                //dp[preCharIndex] 最长前缀长度
                //比之前长1
                if (charArray[index - 1] == charArray[dp[preCharIndex]]) {
                    dp[index] = dp[preCharIndex] + 1;
                    return;
                }
                //继续向前
                preCharIndex = dp[preCharIndex];
            }
        }

        static String randomLetterStr(int len) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = len; i > 0; i--) {
                //0-1小数 0 10double 0-10
                int charValue = 'a' + (int) (Math.random() * 10);
                char charTemp = (char) charValue;
                stringBuilder.append(charTemp);
            }
            return stringBuilder.toString();
        }

        public static void main(String[] args) {
//            int[] ints = kmpHelpArray("aabcaaba");
//            ArrayUtils.print(ints);
            for (int times = 100; times > 0; times--) {
                String str1 = randomLetterStr(50);
                String str2 = randomLetterStr(20);
                int kmp1 = kmpIndexOf(str1, str2);
                int java1 = str1.indexOf(str2);
                if (kmp1 != java1) {
                    System.out.println("随机=====");
                    System.out.println(str1);
                    System.out.println(kmp1);
                    System.out.println(str2);
                    System.out.println(java1);
                    break;
                }
                str2 = str1.substring(25);
                kmp1 = kmpIndexOf(str1, str2);
                java1 = str1.indexOf(str2);
                if (kmp1 != java1) {
                    System.out.println("劫取");
                    System.out.println(str1);
                    System.out.println(kmp1);
                    System.out.println(str2);
                    System.out.println(java1);
                    break;
                }
            }

        }
    }


    static class CoffeeCup {

        static int[] getCoffeeTimeArray(int[] coffeeMachineArray, int num) {
            //存储数组 第一个数字表示 这个咖啡机什么时候可以用，第二个数字表示这个咖啡机多久冲好一杯
            //这个比较器 意味着这个咖啡机什么可以冲好一杯，这样就实现用户聪明的最早的拿到咖啡
            PriorityQueue<int[]> helpQueue = new PriorityQueue<>(Comparator.comparing(item -> item[0] + item[1]));
            //初始的时候 每个咖啡机都是空闲的
            for (int machine : coffeeMachineArray) {
                helpQueue.add(new int[]{0, machine});
            }
            //每个用户什么时候可以拿到咖啡也是每个用户什么时候可以喝完咖啡
            int[] result = new int[num];
            //选择每一个用户
            for (int people = 0; people < num; people++) {
                //最早冲好一杯的咖啡机信息，
                int[] mastFastGetCoffee = helpQueue.poll();
                //这个人什么时候可以拿到咖啡 = 咖啡机什么时候可用+冲好一杯的时间
                result[people] = mastFastGetCoffee[0] + mastFastGetCoffee[1];
                //这个咖啡机被使用 更新一下 空闲时间要加上冲当前这杯的时间
                mastFastGetCoffee[0] += mastFastGetCoffee[1];
                //加入到堆
                helpQueue.add(mastFastGetCoffee);
            }
            return result;
        }

        static int process1(int[] finishCoffee, int free, int a, int b, int index) {
            //加入是最后一个人 那么 他要做出抉择
            //1.用洗咖啡的机器的时间 free+a
            //2.风干
            //选择最小的哪个返回即可
            if (index == finishCoffee.length - 1) {
                //喝完的时间 和 洗杯机 时间的最大值   +  洗一个杯子的时间，
                // 可能机器好了还没喝完 or 喝完了但是机器还没好
                int use = Math.max(free, finishCoffee[index]) + a;
                //不用洗杯机，那么时间就是和完的时间+自然干的时间
                int noUse = finishCoffee[index] + b;
                return Math.min(use, noUse);
            }
            //第index 个人 选择洗杯机洗
            int curPeopleTime1 = Math.max(free, finishCoffee[index]) + a;
            //后续的人 洗完的时间
            //后续的洗杯机 要等待 curPeopleTime1也就是当前这个人洗完杯子之和才能洗
            int nextPeopleTime1 = process1(finishCoffee, curPeopleTime1, a, b, index + 1);
            //第一种方法需要的总时间，要从当前这个人处理完的时间和后面人处理结束的时间取较大者
            //可能后面的人早处理完了，这个人还没做完，也可能这个人早早处理完了后面的还没做完
            int washWay = Math.max(nextPeopleTime1, curPeopleTime1);
            //第index 人选择自然风干
            //自然干那得 喝完才能干 相加
            int curPeopleTime2 = finishCoffee[index] + b;
            //后续的人做完的时间
            int nextPeopleTime2 = process1(finishCoffee, free, a, b, index + 1);
            // 现在自然干的时间 等于当前这个人杯子干的时间 和后续人处理完时间的最大值
            int dryWay = Math.max(curPeopleTime2, nextPeopleTime2);
            //选择最小的
            return Math.min(washWay, dryWay);
        }

        static int process2(int[] finishCoffee, int a, int b) {
            int maxFree = finishCoffee[0] + a;
            int len = finishCoffee.length;
            //估算 最大的洗咖啡杯机器占用时间
            for (int index = 1; index < len; index++) {
                maxFree = Math.max(finishCoffee[index], maxFree) + a;
            }
            int[][] dp = new int[len][maxFree];
            for (int free = 0; free < maxFree; free++) {
                //喝完的时间 和 洗杯机 时间的最大值   +  洗一个杯子的时间，
                // 可能机器好了还没喝完 or 喝完了但是机器还没好
                int use = Math.max(free, finishCoffee[len - 1]) + a;
                //不用洗杯机，那么时间就是和完的时间+自然干的时间
                int noUse = finishCoffee[len - 1] + b;
                dp[len - 1][free] = Math.min(use, noUse);
            }
            //倒数第一行已经初始化了
            for (int row = len - 2; row > 0; row--) {
                for (int free = 0; free < maxFree; free++) {
                    //第index 个人 选择洗杯机洗
                    int curPeopleTime1 = Math.max(free, finishCoffee[row]) + a;
                    //后续的人 洗完的时间
                    //后续的洗杯机 要等待 curPeopleTime1也就是当前这个人洗完杯子之和才能洗
                    int nextPeopleTime1 = dp[row + 1][curPeopleTime1];
                    //第一种方法需要的总时间，要从当前这个人处理完的时间和后面人处理结束的时间取较大者
                    //可能后面的人早处理完了，这个人还没做完，也可能这个人早早处理完了后面的还没做完
                    int washWay = Math.max(nextPeopleTime1, curPeopleTime1);
                    //第index 人选择自然风干
                    //自然干那得 喝完才能干 相加
                    int curPeopleTime2 = finishCoffee[row] + b;
                    //后续的人做完的时间
                    int nextPeopleTime2 = dp[row + 1][free];
                    // 现在自然干的时间 等于当前这个人杯子干的时间 和后续人处理完时间的最大值
                    int dryWay = Math.max(curPeopleTime2, nextPeopleTime2);
                    dp[row][free]=Math.min(washWay,dryWay);
                }
            }
            return dp[0][0];
        }
    }
}
